package cn.lishiyuan.algorithm.hash;


import java.util.Arrays;
import java.util.Objects;

/**
 * 拉链法哈希表
 * @param <K>
 * @param <V>
 */
public class HashTable<K,V> implements LeeMap<K,V> {

    private int size = 0;
    //
    private int capacity = 1 << 4;

    private double loadFactor = 0.75;

    private Entry<K,V>[] table;

    public HashTable() {
        table = new Entry[capacity];
    }

    public static class Entry<K,V> {
        final int hash;
        final K key;
        V value;

        Entry<K,V> prev = null;
        Entry<K,V> next = null;

        public Entry(int hash,K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }


        public K getKey() {
            return key;
        }
        public V getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "{" + key + ":" + value + "}";
        }
    }

    @Override
    public void put(K key, V value) {
        int hash = hash(key);
        int index = hash & (table.length - 1);

        resizeIfNecessary();

        Entry<K, V> kvEntry = new Entry<>(hash, key, value);

        Entry<K,V> entry = table[index];

        if (entry == null) {
            table[index] = kvEntry;
            size++;
            return;
        }

        while (entry != null) {
            // 交换value
            if (entry.hash == hash && entry.key.equals(key)) {
                entry.value = value;
                return;
            }
            if (entry.next == null) {
                // 已在最后一个
                entry.next = kvEntry;
                kvEntry.prev = entry;
                size++;
                return;
            } else {
                entry = entry.next;
            }
        }



    }

    @Override
    public V get(K key) {
        Entry<K, V> entry = getEntry(key);
        return Objects.isNull(entry) ? null : entry.getValue();
    }

    @Override
    public void remove(K key) {
        int hash = hash(key);
        int index = hash & (table.length - 1);

        Entry<K,V> entry = table[index];

        if (entry == null) {
            return;
        }

        while (entry != null) {
            // 交换value
            if (entry.hash == hash && entry.key.equals(key)) {
                if (entry.prev != null) {
                    entry.prev.next = entry.next;
                }
                if (entry.next != null) {
                    entry.next.prev = entry.prev;
                }

                if(table[index] == entry){
                    table[index] = entry.next;
                }

                entry.prev = null;
                entry.next = null;

                size--;
                return;
            }

            entry = entry.next;
        }
    }

    private Entry<K,V> getEntry(K key) {
        int hash = hash(key);
        int index = (table.length - 1) & hash;

        Entry<K,V> entry = table[index];

        while(entry != null){
            if(hash == entry.hash && Objects.equals(entry.key,key)){
                return entry;
            }
            entry = entry.next;
        }

        return null;
    }


    @Override
    public boolean containsKey(K key) {
        Entry<K, V> entry = getEntry(key);
        return Objects.nonNull(entry);
    }

    private static int hash(Object key) {
        // 对折按位与
        if (Objects.isNull(key)) {
            throw new IllegalArgumentException("key can not be null");
        }
        int h;
        return  (h = key.hashCode()) ^ (h >>> 16);
    }

    @Override
    public void clear() {
        Arrays.fill(table, null);
        size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < table.length; i++) {
            Entry<K, V> entry = table[i];
            while (entry != null) {
                sb.append(entry);
                entry = entry.next;
            }
        }
        sb.append("]");

        return sb.toString();
    }

    private void resizeIfNecessary(){
        double threshold = loadFactor * capacity;
        if (size < threshold){
            return;
        }
        // 扩容 ×2
        int newCapacity = this.capacity << 1;
        Entry<K,V>[] newTable = new Entry[newCapacity];

        for (int i = 0; i < table.length; i++) {
            Entry<K, V> entry = table[i];
            if (entry == null) {
                continue;
            }

            while (entry != null) {

                int hash = entry.hash;
                int index = hash & (newTable.length - 1);

                Entry<K, V> kvEntry = entry;

                Entry<K,V> newEntry = newTable[index];

                if (newEntry == null) {
                    newTable[index] = kvEntry;
                    entry = entry.next;
                    continue;
                }
                // 寻找插入位置，插入数据
                while (newEntry != null){
                    if (newEntry.next == null) {
                        // 已在最后一个
                        newEntry.next = kvEntry;
                        kvEntry.prev = newEntry;
                        //
                        entry = entry.next;
                        break;
                    }
                    newEntry = newEntry.next;
                }

            }
        }

        this.table = newTable;
        this.capacity = newCapacity;

    }
}
